﻿\subsection{Умножение}

\subsubsection{Умножение при помощи сложения}

Вот простой пример:

\begin{lstlisting}[style=customc]
unsigned int f(unsigned int a)
{
	return a*8;
};
\end{lstlisting}

Умножение на 8 заменяется на три инструкции сложения, делающих то же самое.
Должно быть, оптимизатор в MSVC решил, что этот код может быть быстрее.

\begin{lstlisting}[caption=\Optimizing MSVC 2010,style=customasmx86]
_TEXT	SEGMENT
_a$ = 8		; size = 4
_f	PROC
; File c:\polygon\c\2.c
	mov	eax, DWORD PTR _a$[esp-4]
	add	eax, eax
	add	eax, eax
	add	eax, eax
	ret	0
_f	ENDP
_TEXT	ENDS
END
\end{lstlisting}

\subsubsection{Умножение при помощи сдвигов}
\label{subsec:mult_using_shifts}

Ещё очень часто умножения и деления на числа вида $2^{n}$ заменяются на инструкции сдвигов.

\begin{lstlisting}[style=customc]
unsigned int f(unsigned int a)
{
	return a*4;
};
\end{lstlisting}

\begin{lstlisting}[caption=\NonOptimizing MSVC 2010,style=customasmx86]
_a$ = 8		; size = 4
_f	PROC
	push	ebp
	mov	ebp, esp
	mov	eax, DWORD PTR _a$[ebp]
	shl	eax, 2
	pop	ebp
	ret	0
_f	ENDP
\end{lstlisting}

Умножить на 4 это просто сдвинуть число на 2 бита влево, 
вставив 2 нулевых бита справа (как два самых младших бита). 
Это как умножить 3 на 100~--- нужно просто дописать два нуля справа.

Вот как работает инструкция сдвига влево:

\myindex{x86!\Instructions!SHL}
\input{shift_left}

Добавленные биты справа~--- всегда нули.

Умножение на 4 в ARM:

\begin{lstlisting}[caption=\NonOptimizingKeilVI (\ARMMode),style=customasmARM]
f PROC
        LSL      r0,r0,#2
        BX       lr
        ENDP
\end{lstlisting}

Умножение на 4 в MIPS:

\lstinputlisting[caption=\Optimizing GCC 4.4.5 (IDA),style=customasmMIPS]{patterns/11_arith_optimizations/MIPS_SLL.lst}

\myindex{MIPS!\Instructions!SLL}
\INS{SLL} это \q{Shift Left Logical}.

\subsubsection{Умножение при помощи сдвигов, сложений и вычитаний}
\label{multiplication_using_shifts_adds_subs}

Можно избавиться от операции умножения, если вы умножаете на числа вроде 7 или 17,
и использовать сдвиги.

Здесь используется относительно простая математика.

\myparagraph{32-бита}

\lstinputlisting[style=customc]{patterns/11_arith_optimizations/mult_shifts.c}

\mysubparagraph{x86}

\lstinputlisting[caption=\Optimizing MSVC 2012,style=customasmx86]{patterns/11_arith_optimizations/mult_shifts_MSVC_2012_Ox.asm}

\mysubparagraph{ARM}

Keil, генерируя код для режима ARM, использует модификаторы инструкции, в которых можно задавать
сдвиг для второго операнда:

\lstinputlisting[caption=\OptimizingKeilVI (\ARMMode),style=customasmARM]{patterns/11_arith_optimizations/mult_shifts_Keil_ARM_O3.s}

Но таких модификаторов в режиме Thumb нет.

И он также не смог оптимизировать функцию \TT{f2()}:

\lstinputlisting[caption=\OptimizingKeilVI (\ThumbMode),style=customasmARM]{patterns/11_arith_optimizations/mult_shifts_Keil_thumb_O3.s}

\mysubparagraph{MIPS}

\lstinputlisting[caption=\Optimizing GCC 4.4.5 (IDA),style=customasmMIPS]{patterns/11_arith_optimizations/mult_shifts_MIPS_O3_IDA.lst}

\myparagraph{64-бита}

\lstinputlisting[style=customc]{patterns/11_arith_optimizations/mult_shifts_64.c}

\mysubparagraph{x64}

\lstinputlisting[caption=\Optimizing MSVC 2012,style=customasmx86]{patterns/11_arith_optimizations/mult_shifts_64_GCC49_x64_O3.s}

\mysubparagraph{ARM64}

GCC 4.9 для ARM64 также очень лаконичен благодаря модификаторам сдвига:

\lstinputlisting[caption=\Optimizing GCC (Linaro) 4.9 ARM64,style=customasmARM]{patterns/11_arith_optimizations/mult_shifts_64_GCC49_ARM64.s}

\myparagraph{Алгоритм умножения Бута}

\myindex{Data general Nova}
\myindex{Алгоритм умножения Бута}
Когда-то компьютеры были большими и дорогими настолько, что некоторые не имели поддержки операции умножения
в \ac{CPU}, например Data General Nova.
И когда операция умножения была нужна, она обеспечивалась программно, например, при помощи алгоритма Бута
(\IT{Booth's multiplication algorithm}).
Это алгоритм перемножения чисел используя только операции сложения и сдвига.

То что ныне делают компиляторы для оптимизации --- это не совсем то,
но цель (умножение) и средства (замена более быстрыми операциями) те же.

